package chart.树的遍历;

import chart.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @data 2021/3/25 11:13
 */
public class TreeDFS {
    public static void main(String[] args) {
        TreeNode<Integer> node1 = new TreeNode<>(1);
        TreeNode<Integer> node2 = new TreeNode<>(2);
        TreeNode<Integer> node3 = new TreeNode<>(3);
        TreeNode<Integer> node4 = new TreeNode<>(4);
        node1.left = node2;
        node1.right = node4;
        node2.left = node3;
        System.out.println(dfs(node1));
    }

    /**
     * 深度优先搜索
     * 一搜到底
     * 使用栈保存节点
     * Depth first search
     * @param root
     * @return
     */
    public static String dfs(TreeNode<Integer> root) {
        StringBuilder ans = new StringBuilder();
        Deque<TreeNode<Integer>> stack = new ArrayDeque<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode<Integer> node = stack.pop();
            ans.append(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return ans.toString();
    }
}
